class SegmentTree:
    """
    callers should use 0-based index
    ranges are both-side included, i.e. [l, r] includes both l and r
    """
    def __init__(self, nums):
        n = len(nums)
        self.d = [0] * (4 * n)
        self.b = [0] * (4 * n)
        self.n = n
        self._build([0] + nums, 1, n, 1)

    def _build(self, a, s, t, p):
        d, b = self.d, self.b
        if s == t:
            d[p] = a[s]
            return
        m = (s + t) // 2
        self._build(a, s, m, 2 * p)
        self._build(a, m + 1, t, 2 * p + 1)
        d[p] = d[2 * p] + d[2 * p + 1]

    def _push_down(self, s, t, p):
        d, b = self.d, self.b
        m = (s + t) // 2
        if b[p] is not None and s != t:
            d[2 * p] = (m - s + 1) * b[p]
            d[2 * p + 1] = (t - m) * b[p]
            b[2 * p] = b[p]
            b[2 * p + 1] = b[p]
            b[p] = None

    def _update(self, l, r, c, s, t, p):
        d, b = self.d, self.b
        if l <= s <= t <= r:
            d[p] = c * (t - s + 1)
            b[p] = c
            return
        m = (s + t) // 2
        self._push_down(s, t, p)
        if l <= m:
            self._update(l, r, c, s, m, 2 * p)
        if m < r:
            self._update(l, r, c, m + 1, t, 2 * p + 1)
        d[p] = d[2 * p] + d[2 * p + 1]

    def update(self, l, r, c):
        self._update(l + 1, r + 1, c, 1, self.n, 1)

    def _get_sum(self, l, r, s, t, p):
        d, b = self.d, self.b
        if l <= s <= t <= r:
            return d[p]
        self._push_down(s, t, p)
        m = (s + t) // 2
        sum_ = 0
        if l <= m:
            sum_ += self._get_sum(l, r, s, m, 2 * p)
        if m < r:
            sum_ += self._get_sum(l, r, m + 1, t, 2 * p + 1)
        return sum_

    def get_sum(self, l, r):
        return self._get_sum(l+1, r+1, 1, self.n, 1)